清华大学龙桂鲁等：量子计算可能对经典对称密码形成致命威胁
最近清华大学、北京量子信息科学研究院龙桂鲁教授、王泽国博士、魏世杰博士和英国南安普顿大学Lajos Hanzo院士提出了一个对称密码算法的量子攻击方案，有可能对DES等对称加密算法形成致命威胁，从而影响对称密码算法在量子计算时代的安全性。
到目前为止，国际上普遍认为，虽然量子计算机对RSA等非对称密码带来致命攻击，而对AES等对称密码并没有形成致命的威胁。对于AES等对称密码，在Grover量子算法攻击下，其计算复杂度从2的n指数（2^n）变到了2的n/2指数（2^(n/2)），依然不改变其指数复杂度。因此，普遍认为，只要将密码长度增加一倍，就可以达到量子计算机下对应的安全性。目前，国际上已启动了密码体系的升级迁移计划。
龙桂鲁教授等提出的新的攻击方法采用变分量子算法(Variational Quantum Algorithm, VQA），他们研究了对称密码算法S-DES（Simplified Data Encryption Standard）在VQA攻击下的安全性。他们根据一段已知的明文及其对应的密文，构建了一个哈密顿量，该哈密顿量的基态对应该密文的量子态，然后通过采用变分的方式去寻找哈密顿的基态，找到了基态，就可以得到加密的密钥。简单地说，VQA就是构造一个量子线路，其中有若干含有参数的量子门，对这些参数进行变分，得到最小值。他们采用了6种含参量子门和2种不同的求极值方法，共12种不同的变分策略进行计算，其结果如文中表2所示。在2种求极值方法中，梯度下降方法比单纯形法更好，平均需要30-56次搜索即得到密钥，这与Grover攻击方法需要的32次差不多。
表2 不同变分策略下的迭代次数比较
虽然平均次数和Grover算法差不多，但是变分方法的搜索次数并不固定，有一个变化区间。在一些情况下，其搜索次数比Grover算法要低得多，甚至低到只有2次的情况。文中图9给出了搜索次数的分布图，对应于表2的第3行（A Y-Cz）的梯度下降法运算。对于相同的哈密顿量和参数，共做了30次重复运算，超过94次还没有收敛的话，就停止搜索。最小的搜索次数是2。搜索次数在2-5次之间时，共有10次，占了三分之一，是一个不小的比例。有3次是在搜索了94次以后没有结果停止的。在实际计算当中，可以把截止搜索次数设定的更低一些，这样就可以有更多的时间去尝试搜索次数小的那些变分方案。
变分计算方法没有确定的复杂度，这是变分算法的一个缺点。但在密码分析中，这种复杂度的不确定性为AES等加密算法在量子计算的攻击下的安全性分析带来严重的挑战，也为基于计算复杂度的整个经典密码算法的安全性分析带来挑战。变分量子算法有可能对这些密码算法形成超越Shor算法和Grover算法的更加严重的攻击。特别是，变分量子算法在近期的量子计算硬件就可以应用。如果本研究的结果在更大规模的密码算法中，如AES-128，依然成立，将进一步强化这一估测，并对未来的信息安全的路线产生重大影响。
值得关注的是，为应对量子计算对RSA等非对称密码的威胁，经典密码发展了后量子密码算法。最近美国国家标准局宣布了第三轮胜出的方案。分析后量子密码在变分量子算法攻击下的安全性，也是一个需要应对的严峻挑战。
采用量子直接通信和量子密钥分发等量子技术可以应对这种挑战。量子直接通信使窃听者得不到任何与信息有关的数据，没有东西可破译，不管破译者有多大的计算能力也无能为力。量子密钥分发使得窃听者得不到任何密钥的信息，利用这些密钥对信息进行一次一密加密，已被证明不可破译。
这一研究成果发表将发表在SCIENCE CHIN Information Sciences 2022年第10期“量子信息专题”上，研究得到了国家重点研究开发计划、国家自然科学基金、北京市科委、教育部等项目的支持。
图9 采用Y-Cz(A)变分和梯度下降算法下的搜索次数,超过94次将不再继续搜索
Zeguo WANG, Shijie WEI, Gui-Lu LONG & Lajos HANZO. Variational quantum attacks threaten advanced encryption standard based symmetric cryptography. Sci China Inf Sci, 65(10): 200503, doi: 10.1007/ s11432-022-3511-5
作者简介
王泽国
清华大学，博士毕业生，将到量子科技长三角产业创新中心工作
魏世杰
北京量子信息科学研究院，助理研究员
龙桂鲁
清华大学，教授
北京量子信息科学研究院，副院长
Lajos Hanzo
University of Southampton, Uk, 教授
英国皇家工程院院士
相关阅读
点击下方阅读原文按钮，免费下载。